# (示例说明：题目编号和提交通过链接一定要有，其次包括标签、解题思路、代码)
# 力扣3440. 重新安排会议得到最多空余时间 II (https://leetcode.cn/problems/reschedule-meetings-for-maximum-free-time-ii)
# 中等题，20250710 每日一题
# [区间类问题] [分类讨论] [前后缀分解]
# 分成两种情况两个问题，然后求最大即可
# 第一种情况是不能搬到外面，跟上一题3439一样(相当于k=1)
# 第二种情况是可以搬到外面，枚举前后缀中的最大空隙，然后枚举中间点
# AC: https://leetcode.cn/submissions/detail/642670515/
class Solution:
    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
        ans1 = self.maxFreeTime1(eventTime, 1, startTime, endTime)
        n, ans2 = len(startTime), 0
        pre, suf = [0] * n, [0] * n
        pre[0] = startTime[0]
        for i in range(1, n):
            pre[i] = max(pre[i - 1], startTime[i] - endTime[i - 1])
        suf[-1] = eventTime - endTime[-1]
        for i in range(n - 2, -1, -1):
            suf[i] = max(suf[i + 1], startTime[i + 1] - endTime[i])
        for i in range(n):
            max_slot = 0
            if i:
                max_slot = pre[i - 1]
            if i < n - 1:
                max_slot = max(max_slot, suf[i + 1])
            if max_slot >= endTime[i] - startTime[i]:
                t = 0
                if i == 0:
                    t = startTime[i + 1]
                elif i == n - 1:
                    t = eventTime - endTime[i - 1]
                else:
                    t = startTime[i + 1] - endTime[i - 1]
                ans2 = max(ans2, t)
        return max(ans1, ans2)
    # 3439. 重新安排会议得到最多空余时间 I
    def maxFreeTime1(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        n = len(startTime)
        a = []
        for i in range(n):
            if i == 0:
                a.append(startTime[i])
            else:
                a.append(startTime[i] - endTime[i - 1])
            if i == n - 1:
                a.append(eventTime - endTime[i])
        ans = sm = sum(a[:k + 1])
        i, j = 0, k + 1
        while j < n + 1:
            sm += a[j] - a[i]
            j += 1
            i += 1
            ans = max(ans, sm)
        return ans

        